#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std; 
#define Status int
#define OK 1
#define ERROR 0

typedef struct{
	char number[10];
	char name[5];
	int score;
}ElemType;

typedef struct LNode{
	ElemType data;		//数据域 
	struct LNode *next; //指针域 
}LNode, *LinkList;

//初始化单链表 
Status InitList_L(LinkList &L){
	L = new LNode;
	//或者
	//L = (LinkList)malloc(sizeof(LNode)); 
	L->next = NULL;
	return OK;
}

//判断链表是否为空 
Status ListEmpty(LinkList L){
	if(L->next){
		return 0;//非空 
	}else {
		return OK;//空 
	}
}

//单链表的销毁  从头指针开始，依次释放所有的节点 
Status DestoryList(LinkList &L){
	LNode *p;//或者 LinkList p; 
	while(L){
		p = L;
		L = p->next; 
		delete(p);
	//或者free(p);
	}
	return OK;
}
 
//清空单链表  链表仍存在，但链表中无元素，成为空链表(头指针和头结点仍然存在)
//算法思路：依次释放所有的结点，并将头结点指针域设置为空 
Status ClearList(LinkList &L){
	LNode *p = L->next;
	LNode *q;
	while(p){
		q = p->next;
		delete(p);
		p = q;
	}
	L->next = NULL;
	return OK;
}

int ListLength(LinkList L){
//	LinkList p = L->next;
	LNode *p = L->next;
	int i = 0;
	while(p){
		i++;
		p = p->next;
	}
	return i;
}

//取值：取单链表中第i个元素的内容 
Status GetElem_L(LinkList L, int i, ElemType &e){ //获取线性表L中的某个元素的内容，通过变量e返回 
	LNode *p = L->next;		//初始化 
	int j = 1;				 
	while(p && j < i){	   //向后扫描，直到p指向第i个元素或p为空	
		p = p->next;
		++j;
	}
	if(!p || j > i) return ERROR;  //第i个元素不存在 
	e = p->data; 	//取第i个元素 
	return OK;
}

//按值查找：根据指定数据获取该数据所在的位置（该数据的地址），返回第一个匹配的结点指针 
LNode *LocateElem_L(LinkList L, ElemType e){
	//在线性表L中查找值为e的数据元素
	//找到，则返回L中值为e的数据元素的地址，查找失败则返回NULL 
	LNode *p = L->next;
//	while(p && p->data != e){
//		p = p->next;
//	}
// 结构体不能直接判等 
	while(p && (p->data.name != e.name || p->data.number != e.number || p->data.score != e.score)){
		p = p->next;
	}
	return p;
}

//按值查找 根据指定的数据获取该数据位置序号
int LocateElemNumber_L(LinkList L, ElemType e){
	//在线性表L中查找值为e的数据元素的位置序号 
	//返回L中值为e的数据元素的位置序号，查找失败返回0 
	LNode *p = L->next;
	int i = 1;
	//下面是伪码，结构体不能直接判等 
//	while(p && p->data != e){
//		p = p->next;
//		i++;
//	}
	if(p){
		return i;
	}else{
		return 0;
	}
} 

//插入  在第i个结点前插入新结点 
Status ListInsert_L(LinkList &L, int i, ElemType e){
	LNode *p = L;
	int j = 0;
	while(p && j < i - 1){
		p = p->next;
		j++;
	}
	if(!p || j > i - 1) return ERROR; 
	LNode *s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK; 
}

//删除: 将线性表L中第i个数据元素删除 
Status ListDelete_L(LinkList &L, int i){
	LNode *p = L;
	int j = 0;
	while(p->next && j < i - 1){
		p = p->next;
		j++;
	}//寻找第i个结点，并令p指向其先驱 
	if(!(p->next) || j > i - 1) return ERROR; //删除位置不合理 
	LNode *q = p->next;  //临时保存被删除结点的地址以备释放 
	p -> next = q->next;
	delete(q);
	return OK;
}

//建立单链表头插法(前插法)
// 1. 从一个空表开始，重复读入数据
// 2. 生成新结点，将读入数据存放到新结点的数据域中
// 3. 从最后一个结点开始依次将各结点插入到链表的前端
// eg:新建链表 L(a,b,c,d,e)  从L->头结点->e  到 L->头结点-> d -> e ..... 
void CreateList_H(LinkList &L, int n){
	L = new LNode; // L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL; //先建立一个带头结点的单链表 
	while(n) {
		--n;
		LNode *p = new LNode; //生成新结点
		/*cin>>p->data; 伪码*/ 	 //c++语法，p->data伪代码 //输入元素值 scanf(&p->data); 
		p->next = L->next;  //插入到表头 
		L->next = p;
	}
} //时间复杂度 O(n) 


//建立单链表：后插法,尾插法--元素插入到链表尾部，也叫尾插法 
//正位序输入n个元素的值，建立带表头结点的单链表L
//1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
//2.初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点 
void CreateList_R(LinkList &L, int n){
	L = new LNode;
	L->next = NULL;
	LNode *r = L; //尾指针指向头结点 
	while(n){
		n--;
		LNode *p = new LNode;
		/*cin>>p->data; 伪码*/ 		//生成新结点，输入元素值
		p->next = NULL;
		r->next = p;  //p结点插入到表尾 
		r = p; //r指向新的尾结点 
	}
} //CreateList_R
//算法的时间复杂度是O(n) 

int main(void)
{ 
	cout<<"单链表的基本操作\n2021/12/24"<<endl;
	system("pause");
	return 0;
}
